#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
// 最长等差数列：https://leetcode.cn/problems/longest-arithmetic-subsequence/description/
using namespace std;
class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n=nums.size();
        if(n==1) return 1;
        else if(n==2) return 2;
        unordered_map<int,int> hash;
        vector<vector<int>> dp(n,vector<int>(n,2));
        hash[nums[0]]=0;
        int ret=2;
        //固定第二个元素
        for(int i=1;i<n-1;i++)
        {
            //枚举最后一个元素
            for(int j=i+1;j<n;j++)
            {
                int d=nums[j]-nums[i];
                if(hash.count(nums[i]-d)&&hash[nums[i]-d]<i)
                { 
                    dp[i][j]=max(dp[i][j],dp[hash[nums[i]-d]][i]+1);
                }     
                ret=max(ret,dp[i][j]);
            }
            hash[nums[i]]=i;
        }
        return ret;
    }
};